package com.explorati.dongtaiguihua.LeetCode198.HouseRobber;

import java.util.Arrays;

/**
 * 198. House Robber
 * 
 * 暴力解法：检查所有房子的组合，对每一个组合，检查是否有相邻的房子，如果没有，记录其价值。找最大值.O((2^n)*n)
 * 
 * 记忆化搜索解法
 * 
 * @author explorati
 *
 */
class Solution {
	static int[] memo;

	public static int rob(int[] nums) {
		memo = new int[nums.length];
		Arrays.fill(memo, -1);
		return tryRob(nums, 0);
	}

	// 考虑偷取[index...nums.size() - 1]
	private static int tryRob(int[] nums, int index) {
		if (index >= nums.length) {
			return 0;
		}
		if (memo[index] != -1) {
			return memo[index];
		}
		int res = 0;
		for (int i = index; i < nums.length; i++) {
			res = Math.max(res, nums[i] + tryRob(nums, i + 2));
		}
		memo[index] = res;
		return res;
	}

	public static void main(String[] args) {
		int[] nums = { 1, 2, 4, 1 };
		System.out.println(rob(nums));
		String str = "abs";
		StringBuilder sb = new StringBuilder(str);
		sb.insert(1, "f");
		System.out.println(sb.toString());
	}
}
